#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    //剑指 Offer 32 - III. 从上到下打印二叉树 III
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr)
        {
            return {};
        }
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        int flag = -1;
        while (!q.empty())
        {
            vector<int> tmp;
            int size = q.size();
            for (int i = 0; i<size; ++i)
            {
                TreeNode* cur = q.front();
                q.pop();

                tmp.push_back(cur->val);
                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
            }
            if (flag == 1)
                reverse(tmp.begin(), tmp.end());
            ans.push_back(tmp);
            flag *= -1;
        }
        return ans;
    }

    //剑指 Offer 26. 树的子结构
    bool SerchTree(TreeNode* A, TreeNode* B)
    {
        if (A == nullptr && B != nullptr)
        {
            return false;
        }

        if (B == nullptr)
        {
            return true;
        }
        return (A->val == B->val) && SerchTree(A->left, B->left) && SerchTree(A->right, B->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == nullptr || B == nullptr)
        {
            return false;
        }

        if (SerchTree(A, B))
        {
            return true;
        }

        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};